public class Test397 {
    public static void main(String[] args) {
        int i = integerReplacement(33);
        System.out.println();
        System.out.println(i);
    }

    /**
     * 给定一个正整数 n ，你可以做如下操作：
     *
     * 如果 n 是偶数，则用 n / 2替换 n 。
     * 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
     * n 变为 1 所需的最小替换次数是多少？
     * @param n
     * @return
     */
    public static int integerReplacement(int n) {
        if(n==1 || n==2){
            return 1;
        }
        if (n==3){
            return 2;
        }
        int[] cache = new int[(n+1)/2+2];
        cache[1] = 1;
        cache[2] = 1;
        cache[3] = 2;
        int index = 4;
        while (index * 2 <= n+1){
            if(index %2 == 0){
                cache[index] = cache[index/2]+1;
            }else {
                cache[index] = Math.min(cache[(index-1)/2],cache[(index+1)/2])+2;
            }
            index++;
        }
        return n%2 == 0?cache[n/2]+1:Math.min(cache[(n-1)/2],cache[(n+1)/2])+2;
    }
}
